//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
//
// 
//
// 示例： 
//
// 输入：1->2->4, 1->3->4
//输出：1->1->2->3->4->4
// 
// Related Topics 链表

package leetcode.editor.cn;

public class MergeTwoSortedLists {
    public static void main(String[] args) {
        Solution solution = new MergeTwoSortedLists().new Solution();
        ListNode listNode = constructList(new int[]{1, 2, 4});
        ListNode listNode2 = constructList(new int[]{1, 3, 4});
        ListNode node = solution.mergeTwoLists(listNode, listNode2);
        printList(node);
    }

    static ListNode constructList(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }

        ListNode head = null;
        ListNode tail = null;
        for (int i = 0; i < array.length; i++) {
            if (head == null) {
                head = new ListNode(array[i]);
                tail = head;
            } else {
                ListNode node = new ListNode(array[i]);
                tail.next = node;
                tail = node;
            }
        }

        return head;
    }

    static void printList(ListNode node) {
        if (node == null) {
            return;
        }

        while (node != null) {
            System.out.println(node.val);
            node = node.next;
        }

        System.out.println("-------------------end ");
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode p = l1;
            ListNode q = l2;

            ListNode tail = null;

            if (p == null) {
                tail = l2;
                return tail;
            }
            if (q == null) {
                tail = l1;
                return tail;
            }
            ListNode head = tail;

            while (p != null && q != null) {
                int valP = p.val;
                int valQ = q.val;

                if (valP <= valQ) {
                    if (head == null) {
                        head = p;
                        tail = p;
                    } else {
                        tail.next = p;
                        tail = p;
                    }

                    p = p.next;
                } else {
                    if (head == null) {
                        head = q;
                        tail = q;
                    } else {
                        tail.next = q;
                        tail = q;
                    }
                    q = q.next;
                }
            }

            if (p == null) {
                tail.next = q;
            }

            if (q == null) {
                tail.next = p;
            }

            return head;
        }


    }

    //leetcode submit region end(Prohibit modification and deletion)
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}